package com.smh;

import org.junit.jupiter.api.Test;

import javax.swing.tree.TreeNode;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * @author shiminghui
 * @date 2025/2/26 16:02
 * @description: TODO
 */
public class _033_二叉搜索树 {

    @Test
    public void test() {
        BSTree<Integer, Integer> bstree = new BSTree<>();

        bstree.put(4, 4);
        bstree.put(2, 2);
        bstree.put(8, 8);
        bstree.put(7, 7);
        bstree.put(9, 9);
        bstree.put(5, 5);
        bstree.put(6, 6);

        System.out.println(bstree.get(4));
        System.out.println(bstree.getMin());
        System.out.println(bstree.getMax());
        System.out.println(bstree.getPreNodeValue(4));
        System.out.println(bstree.getPostNodeValue(4));
        System.out.println(bstree.delete2(4));
    }

    @Test
    public void test2() {

        BSTree<Integer, Integer> bstree = new BSTree<>();
        bstree.put(4, 4);
        bstree.put(2, 2);
        bstree.put(8, 8);
        bstree.put(7, 7);
        bstree.put(9, 9);
        bstree.put(5, 5);
        bstree.put(6, 6);
        System.out.println(bstree.between(4, 8).toString());
        System.out.println(bstree.greater(4).toString());
        System.out.println(bstree.less(4).toString());

    }

    @Test
    public void test3() {
        BSTree<Integer, Integer> bstree = new BSTree<>();
        bstree.put(5, 5);
        bstree.put(3, 3);
        bstree.put(6, 6);
        bstree.put(2, 2);
        bstree.put(4, 4);
        bstree.put(7, 7);
        System.out.println(bstree.delete(0));
        System.out.println(bstree.isValidBST());
        System.out.println(bstree.isValidBST2());
        System.out.println(bstree.isValidBST());
        System.out.println(bstree.isValidBST3(Integer.MIN_VALUE, Integer.MAX_VALUE));
    }


    private static class BSTree<K extends Comparable<K>, V> {

        private BSTNode<K, V> root;

        public BSTree() {

        }

        // 上限法
        int index = 0;

        // 最近公共祖先
        public BSTNode<Integer, Integer> lowestCommonAncestor(BSTNode<Integer, Integer> root, BSTNode<Integer, Integer> p, BSTNode<Integer, Integer> q) {
            if (root == null || root == p || root == q) {
                return root;
            }
            if (root.key.compareTo(p.key) > 0 && root.key.compareTo(q.key) > 0) {
                return lowestCommonAncestor(root.left, p, q);
            } else if (root.key.compareTo(p.key) < 0 && root.key.compareTo(q.key) < 0) {
                return lowestCommonAncestor(root.right, p, q);
            } else {
                return root;
            }
        }

        /**
         * 构建二叉搜索树,根据前序遍历
         *
         * @param preorder
         * @return
         */
        public BSTNode<Integer, Integer> bstFromPreorder(Integer[] preorder) {
            return doBst(preorder, Integer.MAX_VALUE); // 这里max取Integer.MAX_VALUE，表示没有最大值，可以插入任何值
        }

        public BSTNode<Integer, Integer> doBst(Integer[] preorder, Integer max) {
            if (index >= preorder.length) {
                return null;
            }
            int res = preorder[index].compareTo(max);
            if (res > 0) {
                return null;
            }
            BSTNode<Integer, Integer> root = new BSTNode<>(preorder[index], null); // 创建根节点
            index++;
            // 递归创建左子树
            root.left = doBst(preorder, root.key);
            // 递归创建右子树
            root.right = doBst(preorder, max);
            return root;
        }

        //分治法
        public BSTNode<Integer, Integer> bstFromPreorder2(Integer[] preorder, Integer start, Integer end) {
            if (start > end) {
                return null;
            }
            BSTNode<Integer, Integer> root = new BSTNode<>(preorder[start], null);
            int index = start;
            // 找到右子树的根节点
            while (index <= end) {
                if (preorder[index] > root.key) {
                    break;
                }
                index++;
            }
            root.left = bstFromPreorder2(preorder, start + 1, index - 1);
            root.right = bstFromPreorder2(preorder, index, end);
            return root;
        }


        /**
         * 将范围内的元素之和返回
         *
         * @param root
         * @param low
         * @param high
         * @return
         */
        public int rangeSumBST(BSTNode<Integer, Integer> root, int low, int high) {
            if (root == null) {
                return 0;
            }
            int res = 0;
            res += rangeSumBST(root.left, low, high);

            if (root.key >= low && root.key <= high) {
                res += root.value;
            }

            res += rangeSumBST(root.right, low, high);
            return res;
        }

        public boolean isValidBST3(K pre, K post) {
            return isValidBST(root, pre, post);
        }

        /**
         * 利用上下限判断判断是否为搜索二叉树
         *
         * @param root 当前节点
         * @param pre  下线
         * @param post 上线
         * @return true or false
         */
        public boolean isValidBST(BSTNode<K, V> root, K pre, K post) {
            if (root == null) {
                return true;
            }
            int left = root.key.compareTo(pre);
            int right = root.key.compareTo(post);
            if (left <= 0 && right >= 0) {
                return false;
            }
            boolean l = isValidBST(root.left, pre, root.key);
            if (!l) {
                return false;
            }
            boolean r = isValidBST(root.right, root.key, post);
            return r;
        }

        /**
         * 判断是否为搜索二叉树，递归判断
         *
         * @return
         */
        public boolean isValidBST2() {
            return isValidBST(root, new BSTNode<>());
        }

        private boolean isValidBST(BSTNode<K, V> root, BSTNode<K, V> pre) {
            if (root == null) {
                return true;
            }
            boolean left = isValidBST(root.left, pre);
            if (!left) {
                return false;
            }
            if (pre.key != null) {
                int res = pre.key.compareTo(root.key);
                if (res >= 0) {
                    return false;
                }
            }
            pre.key = root.key;
            boolean right = isValidBST(root.right, pre);
            return right;
        }

        /**
         * 判断是否为搜索二叉树
         *
         * @return
         */
        public boolean isValidBST() {
            if (root == null) {
                return true;
            }
            BSTNode<K, V> cur = root;
            ArrayDeque<BSTNode<K, V>> stack = new ArrayDeque<>();
            BSTNode<K, V> pre = null;
            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    BSTNode<K, V> pop = stack.pop();
                    if (pre != null) {
                        int res = pre.key.compareTo(pop.key);
                        if (res >= 0) {
                            return false;
                        }
                    }
                    pre = pop; // 记录前驱节点
                    cur = pop.right;
                }
            }
            return true;
        }

        /**
         * 递归实现插入节点
         *
         * @param key
         * @param root
         * @return
         */
        private BSTNode<K, V> insert(K key, BSTNode<K, V> root) {
            if (root == null) {
                return new BSTNode<>(key, null);
            }
            int res = key.compareTo(root.key);
            if (res < 0) {
                root.left = insert(key, root.left);
            } else if (res > 0) {
                root.right = insert(key, root.right);
            } else {
                root.value = null;
            }
            return root;
        }


        /**
         * 查询小于key的元素
         *
         * @param key
         * @return
         */
        public List<V> less(K key) {
            if (key == null || root == null) {
                return null;
            }
            ArrayList<V> list = new ArrayList<>();
            BSTNode<K, V> cur = root;
            ArrayDeque<BSTNode<K, V>> stack = new ArrayDeque<>();
            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    cur = stack.pop();
                    int res = key.compareTo(cur.key);
                    if (res > 0) {
                        list.add(cur.value);
                    } else {
                        break;
                    }
                    cur = cur.right;
                }
            }
            return list;
        }

        /**
         * 查询大于key的元素
         *
         * @param key
         * @return
         */
        public List<V> greater(K key) {
            if (key == null || root == null) {
                return null;
            }
            ArrayList<V> list = new ArrayList<>();
            BSTNode<K, V> cur = root;
            ArrayDeque<BSTNode<K, V>> stack = new ArrayDeque<>();
            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.right;
                } else {
                    cur = stack.pop();
                    int res = key.compareTo(cur.key);
                    if (res < 0) {
                        list.add(cur.value);
                    } else {
                        break;
                    }
                    cur = cur.left;
                }
            }
            return list;
        }

        /**
         * 查询在start和end之间元素的集合
         *
         * @param start
         * @param end
         * @return
         */
        public List<V> between(K start, K end) {
            if (start == null || end == null || root == null) {
                return null;
            }
            ArrayList<V> list = new ArrayList<>();
            BSTNode<K, V> cur = root;
            ArrayDeque<BSTNode<K, V>> stack = new ArrayDeque<>();
            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    cur = stack.pop();
                    int res = start.compareTo(cur.key);
                    int res2 = end.compareTo(cur.key);
                    if (res < 0 && res2 > 0) {
                        list.add(cur.value);
                    } else if (res2 <= 0) {
                        break;
                    }
                    cur = cur.right;
                }
            }
            return list;
        }

        public V delete2(K key) {
            ArrayList<V> list = new ArrayList<>();
            root = doDelete(root, key, list);
            return list.get(0);
        }

        /**
         * 递归删除节点
         *
         * @param node
         * @param key
         * @param list 记录删除节点的值
         * @return 删除节点后剩的子树的根节点
         */
        public BSTNode<K, V> doDelete(BSTNode<K, V> node, K key, ArrayList<V> list) { //TODO 写错了，记得更改
            if (node == null) {
                return null;
            }
            int res = key.compareTo(node.key);
            if (res < 0) {
                node.left = doDelete(node.left, key, list);
                return node;
            } else if (res > 0) {
                node.right = doDelete(node.right, key, list);
                return node;
            }
            // 找到了
            list.add(node.value);
            // 如果当前没有有左节点
            if (node.left == null) {
                return node.right;
            }
            // 如果当前没有有右节点
            else if (node.right == null) {
                return node.left;
            }

            // 有左右节点
            // 找到当前节点的后继节点
            BSTNode<K, V> post = node.right;
            BSTNode<K, V> parent = node;
            while (post.left != null) {
                parent = post;
                post = post.left;
            }

            // 当当前节点的右节点就是后继节点
            if (node.right == post) {
                post.left = node.left;
                return post;
            }
            // 当前节点的右节点不是后继节点
            else {
                post.right = doDelete(node.right, post.key, new ArrayList<V>());
                post.left = node.left;
                return post;
            }
        }

        /**
         * 根据key删除节点
         *
         * @param key
         * @return
         */
        public V delete(K key) {
            if (key == null || root == null) {
                return null;
            }

            BSTNode<K, V> cur = root;
            BSTNode<K, V> parent = null;
            while (cur != null) {
                int res = key.compareTo(cur.key);
                if (res < 0) {
                    parent = cur; //记录当前节点的祖先节点
                    cur = cur.left;
                } else if (res > 0) {
                    parent = cur; //记录当前节点的祖先节点
                    cur = cur.right;
                } else {
                    break;
                }
            }
            if (cur == null) {
                return null;
            }

            // 当删除节点没有左孩子
            if (cur.left == null) {
                shift(parent, cur, cur.right);
            }
            // 当删除节点没有右孩子
            else if (cur.right == null) {
                shift(parent, cur, cur.left);
            }
            // 当删除节点左右孩子都有
            else {
                // 查找当前节点的后继节点
                BSTNode<K, V> post = cur.right;
                BSTNode<K, V> postParent = null;
                while (post.left != null) {
                    postParent = post;
                    post = post.left;
                }
                // 当前节点的右孩子就是后继节点
                if (cur.right == post) {
                    shift(parent, cur, post);
                    post.left = cur.left; // 将当前节点的左孩子赋值给后继节点
                } else {
                    // 不可能有左节点
                    shift(postParent, post, post.right); // 将后继节点的右孩子托付给其父节点
                    shift(parent, cur, post);
                    post.right = cur.right;
                    post.left = cur.left;
                }
            }
            return cur.value;
        }

        /**
         * 删除节点
         *
         * @param parent
         * @param cur
         * @param child
         */
        private void shift(BSTNode<K, V> parent, BSTNode<K, V> cur, BSTNode<K, V> child) {
            if (parent == null) {
                root = child;
            } else if (parent.left == cur) {
                parent.left = child;
            } else {
                parent.right = child;
            }
        }

        /**
         * 查询前驱节点
         *
         * @param key
         * @return
         */
        public V getPreNodeValue(K key) {
            BSTNode<K, V> preNode = getPreNode(key);
            return preNode == null ? null : preNode.value;
        }

        private BSTNode<K, V> getPreNode(K key) {
            if (key == null) {
                return null;
            }
            // 判断当前节点是否存在
            BSTNode<K, V> cur = root;
            BSTNode<K, V> ancestors = null;
            while (cur != null) {
                int res = key.compareTo(cur.key);
                if (res < 0) {
                    cur = cur.left;
                } else if (res > 0) {
                    ancestors = cur; //记录当前节点的祖先节点
                    cur = cur.right;
                } else {
                    break;
                }
            }
            if (cur == null) {
                return null; //当前节点不存在
            }

            // 当前节点没有左子树
            if (cur.left == null) {
                // 查找它从左边来的祖先,在查找的时候已经找到
                return ancestors;
            }

            // 当前节点有左子树
            BSTNode<K, V> max = getMax(cur.left);
            return max;
        }

        /**
         * 查询后驱节点
         *
         * @param key
         * @return
         */
        private BSTNode<K, V> getPostNode(K key) {
            if (key == null) {
                return null;
            }
            BSTNode<K, V> cur = root;
            BSTNode<K, V> ancestors = null;
            while (cur != null) {
                int res = key.compareTo(cur.key);
                if (res < 0) {
                    ancestors = cur;
                    cur = cur.left;
                } else if (res > 0) {
                    cur = cur.right;
                } else {
                    break;
                }
            }
            if (cur == null) {
                return null;
            }
            // 当前节点没有右子树
            if (cur.right == null) {
                return ancestors;
            }
            // 当前节点有右子树
            BSTNode<K, V> min = getMin(cur.right);
            return min;
        }

        public V getPostNodeValue(K key) {
            BSTNode<K, V> postNode = getPostNode(key);
            return postNode == null ? null : postNode.value;
        }

        /**
         * 获取最大值
         *
         * @return 最大值
         */
        public V getMax() {
            if (isEmpty()) {
                return null;
            }
            BSTNode<K, V> max = getMax(root);
            return max == null ? null : max.value;
        }

        public BSTNode<K, V> getMax(BSTNode<K, V> node) {
            BSTNode<K, V> cur = node;
            while (cur != null) {
                if (cur.right == null) {
                    return cur;
                }
                cur = cur.right;
            }
            return null;
        }

        /**
         * 获取最小值
         *
         * @return 最小值
         */
        public V getMin() {
            if (isEmpty()) {
                return null;
            }
            BSTNode<K, V> min = getMin(root);
            return min == null ? null : min.value;
        }

        public BSTNode<K, V> getMin(BSTNode<K, V> node) {
            BSTNode<K, V> cur = node;
            while (cur != null) {
                if (cur.left == null) {
                    return cur;
                }
                cur = cur.left;
            }
            return null;
        }

        /**
         * 插入节点 如果key 已经存在，则更新值，否则插入新节点
         *
         * @param key 唯一值
         * @param t   节点的值
         */
        public void put(K key, V t) {
            if (root == null) {
                root = new BSTNode<>(key, t);
            } else {
                BSTNode<K, V> cur = root;
                BSTNode<K, V> parent = null;
                while (cur != null) {
                    int res = key.compareTo(cur.key);
                    parent = cur;
                    if (res < 0) {
                        cur = cur.left;
                    } else if (res > 0) {
                        cur = cur.right;
                    } else {
                        cur.value = t;
                        return;
                    }
                }
                if (key.compareTo(parent.key) < 0) {
                    parent.left = new BSTNode<>(key, t);
                } else {
                    parent.right = new BSTNode<>(key, t);
                }
            }
        }

        /**
         * 根据key查找节点
         *
         * @param key 唯一值
         * @return 节点的值
         */
        public V get(K key) {
            if (isEmpty()) {
                return null;
            }
            BSTNode<K, V> cur = root;
            while (cur != null) {
                int res = key.compareTo(cur.key);
                if (res < 0) {
                    cur = cur.left;
                } else if (res > 0) {
                    cur = cur.right;
                } else {
                    return cur.value;
                }
            }
            return null;
        }

        /**
         * 递归实现查找节点
         *
         * @param root
         * @param key
         * @return 查找到的节点的值
         */
        private V doGet(BSTNode<K, V> root, K key) {
            if (root == null) {
                return null;
            }
            int res = key.compareTo(root.key);
            if (res < 0) {
                return doGet(root.left, key);
            } else if (res > 0) {
                return doGet(root.right, key);
            } else {
                return root.value;
            }
        }

        /**
         * 判断树是否为空
         *
         * @return true or false
         */
        public boolean isEmpty() {
            return root == null;
        }

        /**
         * 判断节点是否存在
         *
         * @param key 节点
         * @return true or false
         */
        public boolean isExist(K key) {
            if (key == null || isEmpty()) {
                return false;
            }
            BSTNode<K, V> cur = root;
            while (cur != null) {
                int res = key.compareTo(cur.key);
                if (res < 0) {
                    cur = cur.left;
                } else if (res > 0) {
                    cur = cur.right;
                } else {
                    return true;
                }
            }
            return false;
        }

        private static class BSTNode<K, V> {
            private K key;
            private V value;
            private BSTNode<K, V> left;
            private BSTNode<K, V> right;

            public BSTNode(K key, V value) {
                this.key = key;
                this.value = value;
            }

            public BSTNode(K key, V value, BSTNode<K, V> left, BSTNode<K, V> right) {
                this.key = key;
                this.value = value;
                this.left = left;
                this.right = right;
            }

            public BSTNode() {

            }

        }
    }

}
